package 题目集.拓扑排序;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个边数组，一个点数组
 * 问对于每个点，找到能抵达它的最小值。输出这些最小值的编号
 * https://leetcode.cn/problems/loud-and-rich/description/
 */
public class ch02_喧闹和富有 {
    /**
     * dfs思路：{@link 题目集.dfs.图.ch04_喧闹和富有}
     *      反向建边，然后dfs+记忆化找到最小的编号
     * 拓扑排序思路：
     *      1.建图，统计每个点的入度
     *      2.结算所有入度为0的节点信息，并推给它的邻接点
     *      3.重复2，直到所有节点都被结算
     */
    int[] quiet;
    int[] res;
    int[] inDegree;
    int[] queue;
    int head, tail;
    List<Integer>[] graph;

    public int[] loudAndRich(int[][] richer, int[] quiet) {
        res = new int[quiet.length];
        this.quiet = quiet;
        inDegree = new int[quiet.length];
        graph = new List[quiet.length];
        queue = new int[quiet.length];
        for (int i = 0; i < quiet.length; i++) {
            graph[i] = new ArrayList<>();
            res[i] = i;
        }
        for (int[] r : richer) {
            graph[r[0]].add(r[1]);
            inDegree[r[1]]++;
        }
        topoSort();
        return res;
    }

    private void topoSort() {
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0 ) {
                queue[tail++] = i;
            }
        }
        while (head < tail) {
            int curr = queue[head++];
            for (Integer to : graph[curr]) {
                inDegree[to]--;
                if (quiet[res[to]] > quiet[res[curr]]) {
                    res[to] = res[curr];
                }
                if (inDegree[to] == 0) {
                    queue[tail++] = to;
                }
            }
        }
    }

    @Test
    public void test() {
        int[][] richer = {{1, 0}, {2, 1}, {3, 1}, {3, 7}, {4, 3}, {5, 3}, {6, 3}};
        int[] quiet = {3, 2, 5, 4, 6, 1, 7, 0};
        int[] res = loudAndRich(richer, quiet);
        for (int re : res) {
            System.out.print(re + " ");
        }
    }
}
